1
|
- Student: Predrag Kostić
- Br. indeksa: 10245
|
2
|
- U ovom radu, opisan je jedan
stručni savetodavni sistem za raspoređivanje rada u poštanskoj
kompaniji (kompaniji za usluge raznošenja). Taj sistem dodaje
interaktivne konverzaciono-grafičke osobine i potprogram kao
podršku dispečeru u njegovim/njenim zadacima i predlaže odgovarajuću odluku
kada naiđe novi zahtev. Eksperiment sa profesionalnim
dispečerom je takođe prikazan.
|
3
|
- Prevoz je jedna od suštinskih delatnosti unutar mnogih organizacija.
Roba i usluge se distribuiraju
mušterijama preko službe prevoza, pa ova delatnost mora biti efikasno
izvršena. U suštini, efikasnost utiče na smanjenje troškova
operacija i povećanje kvaliteta usluge. Gledano sa strane
dispečera, sposobnost da se nađe dobar kompromis između
ova dva suprotna zahteva je veoma važno pitanje.
- Brojni primeri distribuiranja u “realnom vremenu” mogu se naći u
praksi, kao što su ambulantne ili policijske usluge, usluge slanja
paketa ili kućne dostave, transport hendikepiranih, kao i mnoge
druge. U ovom delu, mi smo se fokusirali na specifičnu oblast: kompaniju za poštanske usluge iz
Montreala. Ovde, pisma moraju biti sakupljena i dostavljena sa jednog
mesta na drugo u uličnoj mreži, tako da zadovolji prioritete
korisnika usluga. Za prioritete
su obično navedeni rokovi maksimalnog vremena preuzimanja i
dostavljanja ( npr. pismo mora biti preuzeto za vreme od 30min, i
dostavljeno u vremenu od 90min.).
|
4
|
- Da bi dosledno zadovoljio zahteve na najbolji mogući način uz
pomoć omogućenog voznog parka, dispečer mora obratiti
pažnju na mnogo različitih faktora, kao što su:
- Trenutna pozicija svakog od vozača,
- Planiran pravac kretanja i raspored svakog vozača (za prethodno
dodeljen zahtev),
- Lokacije za mesto preuzimanja i mesto dostave novog zahteva,
- Distance i vreme putovanja između tačaka preuzimanja i
dostave,
- Karakteristike osnovne transportne mreže.
|
5
|
- Dakle, dispečer je ključni elemenat u kompanijama za poštanske usluge. Nažalost, nije
lako pronaći dobre dispečere, zbog specifičnih veština
koje su neophodne za adekvatno izvršavanje zadatka. Štaviše, potrebno je
dosta vremena za obuku dispečera, a njihova profesionalna karijera
obično traje samo nekoliko godina zbog visokog nivoa napetosti
usled potrebe za pravilnim reagovanjem, kao i zbog brzog i
dinamičnog razvitka sredine.
- Prema tome, razvoj stručnog sistema sposobnog za pomoć
dispečerima vozila je od velike ekonomske važnosti. Međutim,
naše sopstveno iskustvo je pokazalo da je to veoma teško, ako ne i
nemoguće da se formalizuje znanje dispečera (npr. preko
pravila odluke, semantičkih mreža itd.). Stoga, naš sistem je
baziran na tehnikama učenja automata, na detaljnom učenju kroz
primere, gde su primeri odluka sakupljeni i analizirani od strane
sistema i prilagođeni kao proces dispečerovih odluka.
Očigledno, mnogo je lakše uzeti primere odlučivanja
dispečera nego izvući jasna pravila odlučivanja kod njih.
- Potprogram učenja unutar sistema je baziran na modelu neuronskih
mreža. Nakon faze obuke sa stručnjakom, sistem moze predlagati
dispečeru vozače koji bi mogli zadovoljiti novopridošle
zahteve. Naravno, dispečer ima konačnu odluku i slobodan je da
prihvati ili odbije predloge sistema.
|
6
|
- Potprogram učenja je ugrađen u granicama konverzacije sa
ciljem da pomaže dispečeru u njegovim zadacima. U ovom delu,
razmatrani su sledeći problemi:
- Lokalizacija novih zahteva unutar mreže ulica
- Procena vremena putovanja i razdaljine
- Rezultati dodele zahteva određenom vozaču
- Definisanje kriterijuma učinka kod vozača, kao što su
mogućnost zaobilaska, vreme preuzimanja, vreme dostavljanja itd.
- Dinamika potprograma učenja
- Za potrebe testa, prototip je korišćen kao simulator posebnih
događaja, i primenjen je na prethodno sakupljena dokumenta i
zahteve. Ovi podaci potiču iz poštanske kompanije iz Montreala.
- U sledećem, drugom delu, upoznaćemo se sa problemima dodele.
Zatim, deo 3 opisuje sistem dodele i njegove razne delove. Potprogram
učenja je predstavljen u delu 4, i razni eksperimenti sa
profesionalnim dispečerom opisani su u delu 5.
|
7
|
- Posmatrajmo sledeći problem. Kompanija za poštanske usluge primila
je poziv za preuzimanje i dostavu prioritetnog pisma u gradskom
području. Svaki korisnik jasno definiše mesto preuzimanja i
dostave, i maksimalno vreme usluge u svakoj od tačaka. Obzirom da
većina korisnika traži brzu uslugu, putanja i raspored moraju biti
određeni u realnom vremenu. U tako zahtevno osetljivom sistemu,
sistem posmatra kada novi korisnik pozove kancelariju dispečera.U
to vreme, pisma nekih ranijih korisnika su već dostavljena i, prema
tome, više se ne razmatraju. Ostali korisnici su dodeljeni
vozačima, i njihova pisma ili treba da budu preuzeta, ili su na
putu da budu dostavljena. Pored toga,u to vreme, put i raspored za
svakog vozača je poznat. Problem je odlučiti kom vozaču
dodeliti zadatak, i koji put i raspored mu postaviti. U rešavanju ovog
problema, dispečer mora pronaći kompromisno rešenje
između dve stvari: umanjenja troškova i zadovoljenja potrebe
korisnika.
- Dinamički problemi kao što je ovaj i dalje su ostavljeni
ljudima-dispečerima. Međutim, nekoliko algoritama je predloženo
u literaturi, u pojedinim algoritmima na osnovu stečenog znanja
koje su razvili Wilson i Covin ’79, za “dial-a-ride” transportni sistem
u Ročesteru, NY. Dinamički programiran algoritam za
pojedinačno vozilo je takođe, opisao Psaraftis ’80.
|
8
|
- Ipak, pristup ovde pokazan je dosta drugačiji. Razvijen je sistem
sposoban za simulaciju procesa odlučivanja dispečera eksperta,
nakon faze obuke sa ovakvim ekspertom. Zato sistem može lako biti
prilagođen drugim uslovima dodele. Pošto se procedura
odlučivanja može dosta menjati od jedne organizacije do druge,
nosivost sistema je veoma važan faktor ovde.
|
9
|
- Sistem uključuje i potprogram dodele za asistiranje dispečeru
pri njegovim zadacima, kao i potprogram učenja za predloge odluka.
U ovom delu, mi ćemo se ograničiti na razne delove potprograma
dodele. Potprogram učenja biće razmatran u sledećoj
oblasti.
- Slika 1 opisuje tok kontrole između 5 komponenti potprograma
dodele. Ove komponente biće sada opisane redom.
|
10
|
- Unutrašnji prikaz cele mreže ulica u Montrealu nalazi se u sistemu.
Svaki čvor u ovoj mreži predstavlja raskrsnicu ulica a svaka veza
je deo ulice između dve raskrsnice. Unutrašnji prikaz mreže
uključuje
- 20 000 čvorova, 30 000 veza i 6 000 ulica. Zadatak potprograma za
lokalizaciju je da transformiše adresu preuzimanja i dostave u element
na strukturi mreže (npr. Čvor ili vezu). Adresa može biti zadata na
četiri jasno određena načina:
- Građanskom adresom, imenovanjem, građanskim brojem i imenom
ulice,
- Poštanskim kodom,
- Imenom (npr. Montrealski
Univerzitet),
- Raskrsnicom ulica (npr. ugao ulice Saint-Laurent i Sherbrooke)
- Kada je adresa locirana na mreži, njene koordinate su pronađene i
razdaljina i vreme prenosa na drugu adresu mogu biti procenjene.
|
11
|
- Ovde je problem proceniti dužinu najkraćeg puta između dve
adrese u mreži (nadalje, to će se odnositi na “tačnu
razdaljinu”). Dva alternativna pristupa će biti razmatrana ovde:
- Proračunavanje tačne razdaljine između svih parova adresa
u mreži, i njihovo skladištenje u tabeli rastojanja za naredno korišćenje.
- Proračunavanje tačne razdaljine između dve adrese svaki
put kada je to potrebno.
- Prvi pristup nije realan za velike mreže, iz razloga što bi tada tabela
rastojanja bila prevelika da bi bila postavljena u glavnu memoriju (
primetimo da N adresa generišu O(N2) parovnih rastojanja). Sa
druge strane izračunavanje tačne razdaljine “po zahtevu” je
nefunkcionalno zbog mnogo vremena potrošenog na računanje. Procena
najkraće putanje je skupa jer dve tačke mogu biti dosta
udaljene, i specifične potrebe moraju biti uračunate pri
proceni, kao što su jednosmerne ulice i zastoji pri skretanju u levo.
- Kako bi dosledno omogućili kraće vreme izračunavanja,
uzeli smo međupristup tako što smo podelili mrežu ulica na 502 zone
veličine kvadratnog kilometra. Unutar svake zone, najvažnija
raskrsnica je definisana kao “centar” zone. Tačne razdaljine su
izračunate između svakog para centara, i postavljene su u
tabelu rastojanja. Veličina tabele je oko 1MB, i može biti
postavljena u glavnu memoriju
|
12
|
- Da bi odredili tačnu razdaljinu između lokacije 1 u zoni 1 i
lokacije 2 u zoni 2 , korišćena je sledeća relacija:
- Bez obzira na odnos između samih položaja, očekivano je da
odnos između tačnog i Menhetn rastojanja između centra u
zoni 1 i centra u zoni 2 bude približno jednak odnosu između
tačnog i Menhetn rastojanja između lokacije 1 i lokacije 2. Obzirom
da je razdaljina između centara u zoni 1 i zoni 2 poznata, i
Menhetn razdaljina je laka za izračunavanje, mi imamo način za
brzi proračun tačne razdaljine između lokacije 1 i
lokacije 2. Detaljnije, ako postoji smetnja između 2 zone (npr.
industrijsko postrojenje), odnos razdaljina između centara zone 1 i
zone 2, biće veći i dovešće , preko odnosa, do veće
procene između tačnog rastojanja između lokacije 1 i
lokacije 2. Ovakav pristup se pokazao kao veoma brz i dosta precizan. U
slučajevima kada su obe lokacije u istoj zoni, koristi se samo
Menhetn rastojanje.
|
13
|
- Slika 2 pokazuje razliku između tačne i Menhetn razdaljine u
uličnoj mreži. Sivi pravougaonici predstavljaju kuće ili
blokove kuća, a beli delovi između sivih pravougaonika
predstavljaju ulice u mreži. Kao što možemo videti u primeru, tačno
rastojanje je veće od Menhetn rastojanja, jer pri tačnom
računanju moraju se pratiti ulice u mreži, da bi se izbegle
prepreke.
|
14
|
- Kada saznamo rastojanje između dve tačke, vreme prenosa možemo
izvesti na osnovu prosečne brzine kretanja vozila. U sistemu,
brzina je funkcija razdaljine. Zapazimo da kada su dve tačke dosta
udaljene, vozač obično koristi veće ulice, i
prosečna brzina se poveća.
- Funkcija brzine uključuje šest parametara:
- VITMIN, minimalnu brzinu,
- VITMOY, prosečnu brzinu,
- VITMAX, maksimalnu brzinu
- d1,d2 i d3, tri tačke duž ose razdaljine za definisanje funkcije
brzine.
- Sa ovim parametrima, po delovima linearna funkcija brzine, kao što je
prikazano na slici ispod, je definisana:
|
15
|
- Za zadato rastojanje d izmedju dve tačke, prosečna brzina je
zatim brzo određena i vreme prenosa je procenjeno.
- Dodatni parametri su takođe dostupni modelu kao spoljašni faktori
koji deluju na prosečnu brzinu, kao što su:
- Meteorološki uslovi. Vreme prenosa može biti pomnoženo sa koeficijentom između 1 i 5
koji označavaju teža stanja na putevima ( jaku kišu, sneg),
- Produktivnost vozača. Vreme prenosa može biti podeljeno
koeficijentom između 1 i 2, u zavisnosti od vozača.
Koeficijenat 1 je za normalnog, a koeficijenat 2 je za dva puta bržeg od
normalnog.
- Gužva u saobraćaju. Tokom špica, ima mnogo više gužve u
saobraćaju. Vreme prenosa može biti pomnoženo koeficijentom od 1 do
2 da bi se uzeo u obzir i faktor gužve.
- Na osnovu svega toga, vreme prenosa se može prikazati kao:
|
16
|
- Zadatak dispečera je da dodeli novi zahtev nekom od raspoloživih
vozača. Koristeći tehnike opisane u poglavljima 3.2. i 3.3. za
procenu rastojanja i vremena prenosa, sistem može pomagati
dispečeru pri oceni rezultata dodavanja novog zahteva u neku od
postojećih trasa. Na osnovu ovih informacija, mnogo je lakše
dispečeru da donese dobre odluke.
- Očigledno, mnoge dodatne tačke su izvodljive u svakoj trasi,
iz razloga što najveći deo vremena usluge određenog od strane
korisnika nije teško prilagodljiv, već normalno predpostavljen.
Jedini uslov je da tački dostave mora predhoditi tačka
preuzimanja. Prema tome, usvojena ubačena tačka je odabrana u
svakoj trasi tako da minimizuje obilaženje (u vremenu) plus dodatna
kazna za naknadno zadržavanje uneto u trasu sa novim zahtevom. Naime,
ako je tačka preuzimanja +j
zahteva j uneta između servisnih tačaka i i k, tačka
dostavljanja –j zahteva j je ubačena između l i m, i je vreme prenosa između i i j,
troškovi dodavanja bi bili smanjeni na:
|
17
|
- U ovoj formuli, predstavljaju
novo vreme usluge, staro vreme usluge i maksimalno vreme usluge,
respektivno. Prve dve komponente u formuli troškova predstavljaju
zaobilazno vreme za nova mesta preuzimanja i dostave, dok je treći
termin suma naknadnog kašnjenja preko +j,-j i svih ostalih servisnih
tačaka koje nailaze posle +j u trasi (većina promenljivih
od +j i
–j su postavljene na 0). Minimizacija obilaznog vremena je
heuristicki način smanjenja sume poremećaja u trenutnoj trasi.
Sa druge strane, jedna promena obilaznog vremena može izazvati mnogo
zakasnelih usluga u jednoj trasi i nekoliko u drugim trasama, u
zavisnosti od razlike između proračunatog i maksimalnog
vremena usluge. Ovo je u obračunu uzeto kaozadnja stavka u formuli
troškova.
- Slika 4 ilustruje proces dodavanja. Na slici, +j i –j predstavljaju
respektivno tačke preuzimanja i dostave zahteva j, a X predstavlja
zadnju tačku usluge vozača u trenutnom vremenu. Dakle,
vozač je već uslužio tačku X, i krenuo je prema
tački preuzimanja zahteva 1. U to vreme, korisnik 3 poziva servis.
Dodato mesto sa minimalnim troškovima za ovaj novi zahtev je pokazano na
slici. Sa ovim novim zahtevom, planirana vremena usluge u +2, -2 i -1 su
odložena, i ubačena nova vremena usluge u sistem.
|
18
|
|
19
|
- Prezentacija različitih alternativnih trasa je omogućena da
pomogne dispečeru da odabere odgovarajućeg vozača.
Detaljnije, sistem ističe devet karakteristika ili osobina da bi
opisao trasu:
- D.E. Zaobilazno vreme usled novog
zahteva
- P.T. Vreme preuzimanja novog zahteva
- D.T. Vreme dostave novog zahteva
- Avg. P Lat. Prosečno vreme kašnjenja na mesto preuzimanja usled
obaveze zbog umetanja novog zahteva
- Avg. D Lat. Prosečno vreme kašnjenja na mesto dostave usled obaveze
zbog umetanja novog zahteva
- #P Lat. Broj naknadnih zakasnelih usluga na mestima preuzimanja, usled
obaveze zbog umetanja novog zahteva
- #D Lat. Broj naknadnih zakasnelih usluga na mestima dostave, usled
obaveze zbog umetanja novog zahteva
- #Req. Broj zahteva na trasi
- Et. Tr. Odnos praznog vremena prenosa i ukupnog vremena prenosa. Vozilo
ide prazno kada se krece prema tački preuzimanja, i tada nema pošte
u vozilu.
|
20
|
- Ekran 1, koji vidimo na slici 5, rangira vozače ili trase prema
visini karakteristika (primetimo da NN predstavlja produkt neuronskih
mreža, kao što će biti opisano u sledećem delu). Ova slika
prikazuje da je vozač Potvin najbolji vozač za usluživanje
novih zahteva ako uzmemo u obzir zaobilazne karakteristike DE, sa
vremenom obilaska od 2.1 min. Vozač Vincent je drugi sa vremenom
zaobilaska od 3.3 min., itd. Mali prozori su klizni, pa je moguće
videti mesto na rang listi bilo kog vozača u vezi sa bilo kojom
karakteristikom.
|
21
|
- Ekran 2, koji vidimo na slici 6, je alternativni ekran. On pokazuje
rangiranje svih vozača odjednom. Na primer, vozač Rioux je
peti prema vremenu obilaska DE, prvi po vremenu preuzimanja PT, prvi po
vremenu dostave DT, itd. Da napomenemo da slike 5 i 6 predstavljaju
prave ekrane.
|
22
|
- Gledajući ove brojeve, dispečer može odabrati određenog
vozača, klikćući mišem na liniju sa vozačevim
imenom. Po selektovanju, prikazuje se cela trasa, sa specijalnim
zasenčanjem za mesta preuzimanja i dostave novog zahteva.(videti
sliku 7). Na trasi je prikazano planirano i maksimalno vreme usluge za
obe adrese, kao i simbol “>” koji se pojavi između dve vrednosti
kada se detektuje neko kašnjenje.
- Dispečer mora potvrditi trasu. Ako mu se ne sviđa trasa,
omogućene su mu tri mogućnosti. Prvo, on može pomeriti
tačke preuzimanja i dostave na druge lokacije unutar trase, kako bi
našao bolje mesto dodavanja. Kada su tačke pomerene na novu
lokaciju, planirano vreme usluge u svakoj tački duž trase se
automatski koriguje. Dispečer može zatražiti korekciju rang liste
na ekranu 1 i ekranu 2, baziranu na novom mestu dodavanja.
- Druga mogućnost je da poništi selekciju, i vrati se na ekrane 1 i
2 kako bi odabrao novog vozača. Kada dispečer potvrdi odabir
vozača, trasa se trajno menja kako bi uključila novi zahtev.
- Treća mogućnost je ostavljanje zahteva na listu
“neodlučenih” zahteva, i sačekati druge zahteve da dođu
pre konačne odlike.
|
23
|
|
24
|
- Potprogram učenja ima za cilj predlaganje “dobrih” vozača za
usluživanje novih zahteva. Bez ovog potprograma, sistem bi imao
neaktivnu ulogu u pomaganju dispečeru. “Back propagation” neuronska
mreža predstavlja srž potprograma učenja. (za totalni opis ovog
modela pogledati [Rumelhart i McClelland 86]).
- “Backpropagation” mreža je tipično sastavljena od tri sloja
prostih procesorskih jedinica, nazvanih ulazni sloj, skriveni sloj i
izlazni sloj. Svaki sloj je u potpunosti povezan sa sledećim slojem
težinskim vezama. Ulazne vrednosti su prdviđene za ulazni sloj, i
ove vrednosti se prostiru duž težinskih veza do skrivenog sloja gde se
obrađuju. Nakon toga, ponavlja se isti postupak između
skrivenog i izlaznog sloja. Konačne vrednosti smeštene su u
izlaznom sloju, i odgovaraju poslednjoj karakteristici (ili izlazu)
mreže.
- Tokom prostiranja, skrivene i izlazne jedinice transformišu svoje ulaze
putem dobro poznate sigmoidalne aktivacione funkcije [Rumelhart i
McClelland 86]:
|
25
|
- Ne vredi ništa ako je aktivaciona vrednost svake jedinice na intervalu
[0,1] posle procesiranja ulaza od strane sigmoida. Praktično,
aktivaciona vrednost izlaznih jedinica je vrednost izmedju 0 i 1, i ona
je odgovor neuronske mreže na trenutni ulazni vektor.
- Moć “backpropagation” mreža ogleda se u njihovim sposobnostima da
se prilagode težini svojih veza kako bi naučili specifične
zadatke. Algoritam učenja koristi željeni izlazni vektor ili odluke
donete od strane eksperta za svaki ulazni vektor (opisujući
problematičnu situaciju). Kada trenutni izlaz ne odgovara željenom
izlazu, greška se koristi da prilagodi težinu veza između slojeva.
- Mnogi parovi (ulaz,željeni izlaz) su određeni od strane mreže za
svrhe vežbanja. Ovi parovi se obrađuju jedan po jedan od strane
mreže da postepeno prilagode težine dok se ne pojavi konvergencija.
Obično, beznačajno mala greška se podesi između trenutnog
i željenog izlaza kako bi proverili ispravnost mreže, i vežba prestaje
kada se pokazatelj ove greške stabilizuje.
- Iz prethodnog obrazloženja, jasno je da podatak mora prvo biti kodiran u
formu ulaznog vektora za neuronsku mrežu. U našem modelu, svaki ulazni
vektor kodira opis situacije raspodele za svakog vozača
pojedinačno. Ako je n broj vozača, n ulaznih vektora je prema
tome kreirano za svaki novi zahtev. Ulazni vektor odabranog vozača
je dobijen je na osnovu devet kriterijuma ili karakteristika opisanih
u delu 3.5 (zaobilazno vreme,
vreme preuzimanja, vreme dostave, itd.).
|
26
|
- Prema tome, ulazni vektor vozača
j za novi zahtev i je:
- gde je p-ta karakteristika vozača
j za zahtev i , a m je broj karakteristika (u ovom slucaju m=9).
- Veoma je važno da primetimo da svaka vrednost karakteristike nosi mali značaj u sebi. Na
primer, zaobilazno vreme od 15 min. za vozača može biti dobro ili
loše, u zavisnosti od ostalih vozača. Prema tome, informacija je
prosleđena za sve vozače. Ako mi želimo obezbediti
“backpropagation” neuronsku mrežu sa opisom koji uključuje samo po
jednog vozača u trenutku (po redu kako bi smanjilo veličinu
ulaznih vektora), potrebneje da vrednosti karakteristika budu transformisane u nove vrednosti
koje mogu biti protumačene bez obraćanja pažnje na ostale
vozače.
|
27
|
- Mi tako prilagođavamo dve naredne transformacije kako bi postigli
ovaj cilj:
- Prevod. Zadati novi zahtev i i vrednost karakteristike , sledeća transformacija je
prva prilagođena:
- gde je n broj vozača i m broj karakteristika. Za bilo koju
karakteristiku p, za
najboljeg vozača j*, i preostale vrednosti odgovaraju razlici od najbolje
vrednosti. Geometrički, ova transformacija prevodi ulazni vektor
svakog vozača u odnosu na vektor
|
28
|
- Normalizacija. Gornje vrednosti su normalizovane između 0 i 1, na
sledeći način:
|
29
|
- Slika 8 pokazuje tri sloja
neuronske mreže baziranih na kodiranju podataka za m=3 karakteristike.
Za svaku normalizovanu vrednost karakteristike postoji ulazna jedinica. Takođe
postoje tri skrivene jedinice povezane sa svakom ulaznom jedinicom.
Zadnji sloj sastoji se od jedinstvene izlazne jedinice sa ciljem da uslovi višestruke procene
kvaliteta vozača. Primetimo takođe da je ulazni sloj direktno
povezan za skriveni sloj i za izlazni sloj. Direktna veza između
ulaznih i izlaznih jedinica obično nije prisutna u standardnoj
“backpropagation” mreži, ali bolji rezultati su zabeleženi sa ovim
modelom.
|
30
|
- Eksperiment opisan u poslednjem delu odnosi se na ovu mrežnu strukturu.
Ipak, devet ulaznih jedinica je upotrebljeno, t.j. jedna ulazna jedinica
za svaku vrednost karakteristike (pogledati deo 3.5)
- Neuronska mreža je trenirana sa klasičnim “backpropagation”
algoritmom [Rumelhart i McClelland 86]. Svaka odluka eksperta, koji je
ili odabrao ili odbio vozača povezanog sa trenutnim ulaznim
vektorom, iskorišćena je da poboljša tačnost mrežnog odgovora,
i prilagodi težinu veza u slučaju greške. Kao što je pomenuto pre,
greška je bazirana na razlici između odgovora mreže i željenog
odabira. Ovde je željeni odabir postavljen na 1 za vozača odabranog
od strane dispečera, a na 0 za drugačiji slučaj.
- Kada je jednom uvežbana, neuronska mreža može biti prilagođena
novim primerima: odgovor koji je blizu 1 znači da vozač koji
je povezan sa trenutnim ulaznim vektorom je dosta pogodan za usluživanje
novog zahteva, dok vrednost blizu 0 znači suprotno. Primetimo da se
izlazi neuronske mreže pojavljuju na prozoru 1 unutar kliznog ekrana NN
(videti sliku 5).
|
31
|
- Da bi sakupio primere odluka, potprogram dodeljivanja je sada
ugrađen u poseban simulator događaja. Ceo sistem je sproveden
u Turbo-Paskalu i pušten na IBM PS/2 mikroračunaru.
- Dva tipa događaja se mogu javiti tokom simulacije: Događaj
zahteva kada novi zahtev naiđe i događaj vozača kada se
vozač javi sa mesta preuzimanja ili mesta dostave. Događaji
zahteva se čitaju sa ulaznih dokumenata, a događaji
vozača se generišu kada su zahtevi dodeljeni. Tokom simulacije, sat
se pomerao u odvojenim vremenskim koracima zasnovanim na vremenski
najbližem sledećem događaju. Kada je trenutni
događaj događaj
zahteva, simulator se zaustavlja da bi dozvolio ekspertu da dodeli
zahtev (videti deo 3).
|
32
|
- Ekran simulacije pokazan je na slici 9. Mali gornji prozor pokazuje
trenutni događaj, koji je ili događaj zahteva ili događaj
vozača (npr. događaj zahteva). Veliki prozor na sredini ekrana
pokazuje trenutno stanje svih vozača. Ako je vozač slobodan,
njegova trenutna pozicija je označena. U suprotnom, pokazane su polazna i odredišna tačka
vozača. Trenutno vreme usluge na polaznoj tački i
očekivano vreme usluge na odredišnoj tački su takođe
prikazani, kao i maksimalno vreme usluge u svakoj tački. Primetimo
da je očekivano vreme usluge na odredišnoj tački uzeto od
strane simulatora da bi odredilo sledeći događaj, vremenski najbliži.
U trenutnom izvršavanju, očekivano i trenutno vreme usluge su isti,
zato što simulator ne generiše još uvek neki neočekivani
događaj (kao što su neočekivana kašnjenja, kvar na vozilima,
itd.). Konačno, prozor pri dnu ekrana se koristi za nerešene
zahteve.
|
33
|
- Sadašnji sistem dodeljivanja može biti iskorišćen na tri
različita načina, kao što prikazuje slika 10.
- Sakupljanje podataka. Ovde, odluke dispečera se sakupljaju tokom
simulacije i skladište u dokument sa primerima vežbanja i testiranja da
bi se kasnije iskoristili od strane neuronske mreže. Ovaj dokument
sadrži vozače izabrane od strane dispečera za svaki zahtev,
kao i opis situacije dodeljivanja za svakog vozača ( na osnovu
karakteristika iz dela 3.5.).
- Vežba/Testiranje neuronske mreže. Ovaj način korišćenja je
uzet za treniranje ili testiranje neuronske mreže na osnovu dokumenta sa
primerima kreiranog u “sakupljanju podataka”. U delu treniranja, primeri
su iskorišććni da prilagode težine veza. U delu testiranja,
karakteristike mreže se procenjuju poređenjem njenih odluka ( sa
trenutnom grupom težina) sa odlukama dispečera. Kao što je
prikazano na slici 10, ovaj deo uključuje samo potprogram
učenja.
- Predlog vozača. Ovde korisnik može pogledati predloge (prethodno
uvežbane) neuronske mreže da bi dodelio novi dokument ili zahtev. Ako je
tako poželjeno, težina veza neuronske mreže je prilagodjena kada se
konačna odluka razlikuje od vrha rangiranih predloga neuronske
mreže.
|
34
|
|
35
|
- Sa namerom da procenimo ispravnost potprograma učenja, izvršili smo
eksperiment sa profesionalnim dispečerom na grupi zahteva
prikupljenoj u radnom danu kompanije za poštanske usluge iz Montreala.
Ukupno 140 zahteva je sakupljeno od 9.00h do 15.00h, i 12 vozača je
bilo iskorišćeno za usluživanje ovih zahteva.
- S’obzirom na kvalitet usluga, uzete su sledeće pretpostavke:
- Maksimalno vreme preuzimanja zahteva j je postavljeno na vreme zahteva
korisnika j plus 30 minuta (gde vreme zahteva korisnika j predstavlja
vreme poziva)
- Maksimalno vreme dostave zahteva j je postavljeno na vreme zahteva
korisnika j plus 90 minuta.
- Iz toga, kašnjenja na tačkama preuzimanja i dostave +j i –j su
računata na sledeći način:
|
36
|
- Prema tome, dispečer je podelio 140 zahteva redom na 12
vozača. Na kraju, 140*12=1680 ulaznih vektora je bilo
omogućeno za uvežbavanje i testiranje neuronske mreže. Mi smo
iskoristili 90 zahteva za uvežbavanje mreže i 50 zahteva za testiranje.
Karakteristike mreže na grupi za testiranje su procenjene
upoređivanjem, za svaki zahtev, rangiranja od strane neuronske
mreže i vozača izabranog od strane dispečera. Ovo rangiranje
je određeno sortiranjem izlaza neuronske mreže za sve vozače u
opadajućem redu.
- Na primer, pretpostavimo da su sortirani izlazi neuronske mreže za n=5
vozača:
- Vozač 1: 0.9
- Vozač 4: 0.8
- Vozač 3: 0.6
- Vozač 5: 0.4
- Vozač 2: 0.1
- Ako je izabran vozač 4 od strane dispečera, rangiranje dato od
neuronske mreže za ovaj izbor je 2.
|
37
|
- Ova rangiranja su prikazana u tabeli 1 za 50 zahteva u grupi za
testiranje. Težine veza neuronske mreže se dobiju posle 100.000
težinskih korigovanja ili ponavljanja učenja na grupi zahteva za
učenje (počinjuci sa slučajnim težinama). Učenje
mreže na 486 IBM PS/2 trajalo je
24 sata.
|
38
|
- Tabela 1 prikazuje da je 80% vozača odabrano od strane eksperta
rangirano kao prvi, drugi ili treći od strane neuronske mreže (t.j.
40 odluka od 50). Štaviše, 94% vozača je rangirano kao prvi, drugi,
treći ili četvrti od strane neuronske mreže. Ove cifre
pokazuju da neuronska mreža može biti veoma korisna da odstrani
vozače, i usmeri pažnju dispečera na najinteresantnije
mogućnosti.
- Nebitno je da li je dosta podjednako dobrih (podjednako loših)
mogućnosti omogućeno ako se ne podudaraju izbori neuronske
mreže i eksperta. U ovakvim situacijama, mreža uvek odabere
prihvatljivog vozaća (t.j. nema “budalastih” izbora).
|
39
|
- Takođe smo iskoristili naučenu mrežu da dodeljuje celu grupu
zahteva jedan po jedan. Tada smo upoređivali trase neuronske mreže
i trase dispečera, prema sledećim merama učinka:
- Produktivnost. Mera produktivnosti upoređuje ukupno vreme putovanja
na trasi sa sumom direktnih vremena putovanja između tačaka
preuzimanja i dostave za svaki zahtev na trasi. Kasniji slučajevi
odgovaraju situaciji kada je svaki zahtev uslužen od strane posebnog
vozila (kao taxi služba).
- U formuli ispod, produktivnost trase r je definisana kao odnos ove dve
vrednosti. Primetimo da je u brojiocu suma direktnih vremena putovanja
svih zahteva u u trasi.
- Odnos praznog vremena putovanja i ukupnog vremena putovanja
- Suma kašnjenja na mestima preuzimanja (u minutima)
- Suma kašnjenja na mestima dostave (u minutima)
|
40
|
- Kriva ispod pokazuje razvoj ovih vrednosti sa dodelom zahteva od strane
mreže ili od strane eksperta. X-osa predstavlja broj odluka dodele, a
Y-osa mere učinka pod analizom. Vrednosti su snimane posle svake
sekvence od deset odluka i sabrane su. Na primer, mera produktivnosti
kod 30-e odluke dodele je prosek uzet od svih trasa, posle dodavanja
30-og zahteva. U ovom procesu, svi dodeljeni zahtevi doprinose proseku.
- Na svakoj slici, krive neuronske mreže su one sa malim krugovima, a
krive dispečera su one sa malim kvadratićima. Kao što možemo
videti, neuronska mreža pokazala se dobro u odnosu na prazno vreme
putovanja, produktivnost, i kašnjenja na mesta preuzimanja. Ipak,
ekspert je bolji u odnosu na kašnjenja na mesta dostave.
Najčešće, trase neuronske mreže imaju dve zakasnele usluge na
mestima preuzimanja (oko 5 minuta u svakom mestu), i tri zakasnele
usluge na mestima dostave (oko deset minuta nu svakom mestu). Sa druge
strane, trase dispečera imaju tri zakasnele usluge na mestima
preuzimanja, i samo jednu zakasnelu uslugu na mestima dostave.
- Prema tome, neuronska mreža se pokazala dosta dobro prema merama
učinka. Čak iako se nije pokazala kao dispečer u odnosu
na ukupna kašnjenja na mestima dostave, vrednosti neuronske mreže su
veoma impresivne. Takođe, dispečer je pritisnut zbog važnosti
dolaska u pravo vreme na mesto preuzimanja (korisnici ne vole da vide
pismo na svome stolu dugo vremena po pozivu postanske kompanije!).
Interesantno je da je neuronska mreža uradila veoma dobar posao u tom
pogledu.
|
41
|
|
42
|
- Sistem predstavljen u ovom radu je razvijen da predstavi upotrebljivost
tehnologije neuronskih mreža u zadacima dodele vozila. Međutim,
sistemu su potrebne dodatne osobine kako bi bio koristan u realnom
ambijentu. Na primer, trenutna pozicija svakog vozača treba biti
lakše korigovana (idealno bi bilo preko ‘on-board’ kompjutera), i
revizija trasa trebala bi biti omogućena u slučajevima dugog
neočekivanog kašnjenja.
- U odnosu na potprogram učenja, faza vežbanja uzima dosta vremena,
ali to nije toliko bitno, zato što to može biti urađeno sa unapred
sakupljenim primerima odluka (kao što smo mi uradili u našim
eksperimentima). Kada se nauči, mreža reaguje veoma brzo, i može
biti upotrebljena u realnoj sredini.
- Konačno, ne vredi ništa ako potprogram učenja uradi dobro, ako
nije u saglasnosti sa procenjenim
vremenom putovanja i razdaljinama. Dispečer je uvideo da su vremena
putovanja veoma realna u većini slučajeva, ali je
očigledno da ove procene predstavljaju dodatni hendikep za
potprogram učenja.
|